﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0192_FindMedianSortedArrays : IAlgorithm
    {
        // 4. 寻找两个正序数组的中位数

        // 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
        // 算法的时间复杂度应该为 O(log (m+n)) 。

        // 提示：
        //  nums1.length == m
        //  nums2.length == n
        //  0 <= m <= 1000
        //  0 <= n <= 1000
        //  1 <= m + n <= 2000
        //  -10^6 <= nums1[i], nums2[i] <= 10^6

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            //Console.WriteLine(Algorithm());
        }

        // 算法
        //nums1 = [1,3], nums2 = [2]
        //nums1 = [1,2], nums2 = [3,4]
        //nums1 = [1,3], nums2 = [2,4]
        //nums1 = [1,2,3,4,5,6,7], nums2 = [1,2]
        public double FindMedianSortedArrays(int[] nums1, int[] nums2)
        {
            int n = nums1.Length;
            int m = nums2.Length;
            int left = (n + m + 1) / 2;
            int right = (n + m + 2) / 2;
            //将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k 。
            return (GetKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + GetKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
        }

        private int GetKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k)
        {
            int len1 = end1 - start1 + 1;
            int len2 = end2 - start2 + 1;
            //让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1 
            if (len1 > len2) return GetKth(nums2, start2, end2, nums1, start1, end1, k);
            if (len1 == 0) return nums2[start2 + k - 1];

            if (k == 1) return Math.Min(nums1[start1], nums2[start2]);

            int i = start1 + Math.Min(len1, k / 2) - 1;
            int j = start2 + Math.Min(len2, k / 2) - 1;

            if (nums1[i] > nums2[j])
            {
                return GetKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
            }
            else
            {
                return GetKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
            }
        }
    }
}
